package chapter02;

public class AddBinary67 {
    /**
     * 模拟竖式计算
     * 将字符串a,b逆序转为数组 方便进位计算
     * arr1存放最长字符串的字符 arr2存放最短字符串的字符
     * pre为前一位的进位值 pre=0
     * i->[0,arr1.length-1]
     *  arr1[i]=(arr1[i]+pre+(i<arr2.length?arr2[i]:0))%2
     *  pre=(arr1[i]+pre+(i<arr2.length?arr2[i]:0))/2
     * 循环结束
     *  a) 如果pre>0
     *     说明循环结束还有一个进位需要加上去
     *     新建数组res 长度arr1.length+1
     *     res[0]=pre 将arr1逆序依次放入res中
     *  b) 直接将arr1逆序 将arr1返回
     */
    public String addBinary(String a, String b) {
        int aLength=a.length();
        int bLength=b.length();
        char[] arr1=new char[aLength>bLength?aLength:bLength];
        char[] arr2=new char[aLength<bLength?aLength:bLength];
        fill(arr1,aLength>=bLength?a:b);
        fill(arr2,aLength>=bLength?b:a);
        int pre=0;
        for(int i=0;i<arr1.length;i++){
            int item=(arr1[i]-'0'+pre+(i<arr2.length?arr2[i]-'0':0));
            arr1[i]=(char)(item%2+'0');
            pre=item/2;
        }
        if(pre>0){
            char[] res=new char[arr1.length+1];
            res[0]=(char)(pre+'0');
            int index=1;
            for(int i=arr1.length-1;i>=0;i--){
                res[index++]=arr1[i];
            }
            return String.valueOf(res);
        }else{
            for(int i=arr1.length-1,j=0;i>j;i--,j++){
                char c=arr1[i];
                arr1[i]=arr1[j];
                arr1[j]=c;
            }
            return String.valueOf(arr1);
        }
    }

    public void fill(char[] arr,String s) {
        for(int i=0;i<arr.length;i++){
            arr[i]=s.charAt(arr.length-i-1);
        }
    }
}
